Caching of data in fast memory is a technique widely used in computer systems to improve performance. Caching is usually done between levels of a memory hierarchy, where data must be transferred from slower, secondary storage "up" to faster, primary storage for use. The transfer of data from slow to fast storage usually happens automatically and invisibly to the application requesting data. The cache algorithm reads requested data from slow memory if it is not in cache, causing the application to wait, or immediately responds if the requested data is in cache by returning the fast memory address of the data. The terms paging and buffering are also used to refer to data caching.
One example of a data cache found in almost every operating system is the paging mechanism for virtual memory management. In this case, data objects are program pages, and the cache is a "working set" of pages kept in main memory when the process is executing. Another common use of data caching is in database or file systems, particularly client-server systems that cache data at the client. Much work on data caching has been done and can be found in operating systems or database textbooks. Two major aspects of any cache management algorithm are its replacement policy and prefetch policy, which both affect efficiency of the cache.
Since a cache is kept full, any new data object transferred from secondary storage to the cache must replace some other object. A cache management algorithm chooses a data object for eviction according to some replacement policy. Many replacement policies have been studied in computer science literature. Most replacement policies in commercial systems are variations or approximations of the Least-Recently-Used (LRU) policy, which stipulates that the object evicted is that object which was used least recently. In the literature, such policies are often compared to a proven optimal policy known as OPT. OPT stipulates that the object evicted from cache is that object which is used furthest in the future. However, this requires perfect and complete knowledge of the future access sequence, so OPT is therefore considered impossible to implement.
Cache management either operates by demand fetching, in which case all objects must be requested by the application program before being brought into cache, or it implements some policy for prefetching objects. The most common prefetch policy is to cluster objects that are often used together near each other on secondary storage, and then fetch an entire cluster of objects into cache when any object in the cluster is requested. Defining how objects should be clustered is considered a relatively difficult problem to solve automatically, and any given clustering necessarily favors some access patterns over others. A prefetched cluster often includes many objects that do not get used, but includes no information to guide the replacement policy in choosing between unused objects for eviction: A second prefetch policy sometimes used is to augment the cache manager with code that uses knowledge of application semantics to prefetch data. For example, an application that displays 3-D spatial data might implement a prefetch heuristic that fetches objects nearest the requested object in a cartesian coordinate system.